package com.wp.targetOffer;

/**
 * Created by 王萍 on 2017/7/28 0028.
 */

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如
 * 数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
 * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
 */
public class 旋转数组的最小数组 {

    public static void main(String[] args) {

//        int[] array = {3, 4, 5, 1, 2};
//        int[] array = {5, 8, 9, 4, 5};
        int[] array = {1, 1, 1, 0, 1};
        int min = minNumberInRotateArray(array);
        System.out.println(min);
    }

    public static int minNumberInRotateArray(int[] array) {
        int left = 0, right = array.length - 1;
        int middle;
        while (right - left != 1) {
            middle = (left + right) / 2;
            if (array[left] == array[middle] && array[middle] == array[right]) {
                int result = array[left];
                for (int i = left + 1; i < right; i++) {
                    if (result > array[i]) {
                        result = array[i];
                    }
                }
                return result;
            }
            if (array[middle] >= array[left]) {
                left = middle;
            }
            if (array[middle] <= array[right]) {
                right = middle;
            }
        }
        return array[right];
    }


    public static int minNumberInRotateArray2(int[] array) {
        int low = 0;
        int high = array.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (array[mid] > array[high]) {
                low = mid + 1;
            } else if (array[mid] == array[high]) {
                high = high - 1;
            } else {
                high = mid;
            }
        }
        return array[low];
    }
}
